package com.xyj.week05;

import com.xyj.common.TreeNode;

/**
 * @author GuXiaoYao
 * @version 1.0.0
 * @since 2021/9/13
 */
public class T7 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder,0,inorder.length-1
                ,postorder,0,postorder.length-1);
    }

    public TreeNode build(int [] inorder,int inorderStart,int inorderEnd,int [] postorder,int postStart,int postEnd){
        if (inorderStart > inorderEnd) {
            return null;
        }
        // 对于后序遍历来说，最后一个数就是根节点
        int maxValue=postorder[postEnd];
        //
        int index=-1;

        // 找到根节点在中序数组中的索引
        for(int i=inorderStart;i<=inorderEnd;i++) {
            if(inorder[i]==maxValue){
                index=i;
                break;
            }
        }
        int leftSize=index-inorderStart;
        // 构建root节点
        TreeNode root=new TreeNode(maxValue);
        root.left=build(inorder,inorderStart,index-1,postorder,postStart,postStart+leftSize-1);
        root.right=build(inorder,index+1,inorderEnd,postorder,postStart+leftSize,postEnd-1);
        return root;
    }
}
